1. Field of the Invention
The present invention relates to an encoding apparatus for transforming data such as video data and audio data, for example, the MPEG method (high quality moving picture encoding system by Moving Picture Coding Experts Group), to a bit stream composed of variable length data, and to a decoding apparatus of the same, and more particularly relates to an encoding apparatus and a decoding apparatus for carrying out encoding and decoding at a high speed by parallel processing and methods of the same.
2. Description of the Related Art
First, an explanation will be made of the MPEG method (MPEG1 and MPEG2)—the standard encoding and decoding system of images currently in general used.
FIG. 1 is a view of the structure of image data in the MPEG method.
As shown in FIG. 1, the image data of the MPEG method is comprised in a hierarchical structure.
The hierarchy is, in order from the top, a video sequence (hereinafter simply referred to as a “sequence”), groups of pictures (GOP), pictures, slices, macroblocks, and blocks.
In MPEG encoding, the image data is sequentially encoded based on this hierarchical structure so as to be transformed to a bit stream.
The structure of a bit stream of MPEG encoded data is shown in FIG. 2.
In the bit stream of FIG. 2, each picture has j number of slices, and each slice has i number of macroblocks.
Further, each level of data other than the blocks in the hierarchy shown in FIG. 1 has a header in which an encoding mode etc. are stored. Accordingly, when describing the structure of a bit stream from the headers of the video sequence, it becomes a sequence header (SEQH) 151, a GOP header (GOPH) 152, a picture header (PH) 153, a slice header (SH) 154, a macroblock header (MH) 155, compressed data (MB0) 156 of a macroblock 0, a macroblock header (MH) 157, and compressed data (MB1) 158 of a macroblock 1.
Note that the size of the compressed data of a macroblock contained in a bit stream is of a variable length and differs depending on the nature of the image etc.
In MPEG decoding, this bit stream is sequentially decoded and the image is reconstructed based on the hierarchical structure of FIG. 14.
Next, the structure of a processing unit for carrying out the encoding and the decoding by the MPEG method, the processing algorithms, and the flow of the processing will be concretely explained.
First, an explanation will be made of the encoding.
FIG. 3 is a block diagram of the configuration of a general processing unit for carrying out MPEG encoding.
An encoding apparatus 160 shown in FIG. 3 has a motion vector detection unit (ME) 161, a subtractor 162, a Fourier discrete cosine transform (FDCT) unit 163, a quantization unit 164, a variable length coding unit (VLC) 165, an inverse quantization unit (IQ) 166, an inverse discrete cosine transform (IDCT) unit 167, an adder 168, a motion compensation unit (MC) 169, and an encode control unit 170.
In an encoding apparatus 160 having such a configuration, when the encoding mode of the input image data is a P (predictive coded) picture or B (bidirectionally predictive coded) picture, the motion compensation prediction is carried out in units of macroblocks at the motion vector detection unit 161, a predicted error is detected at the subtractor 162, DCT is carried out with respect to the predicted error at the discrete cosine transform unit 163, and thereby a DCT coefficient is found. Further, when the encoded picture is an I (Intra-coded) picture, the pixel value is input to the discrete cosine transform unit 163 as it is, DCT is carried out, and thereby the DCT coefficient is found.
The found DCT coefficient is quantized at the quantization unit 164 and subjected to variable length coding together with the motion vector or encoding mode information at the variable length coding unit 165, whereby an encoded bit stream is generated. Further, the quantized data generated at the quantization unit 164 is inversely quantized at the inverse quantization unit 166, subjected to IDCT at the inverse discrete cosine transform unit 167 to be restored to an original predicted error, and added to a reference image at the adder 168, whereby a reference image is generated at the motion compensation unit 169.
Note that, the encode control unit 170 controls the operation of these parts of the encoding apparatus 160.
Such encoding is generally roughly classified into processing at three processing units, that is, the encoding from the motion vector detection at the motion vector detection unit 161 to the quantization at the quantization unit 164, the variable length coding in the variable length coding unit 165 for generating the bit stream, and the local decoding from the inverse quantization in the inverse quantization unit 166 to the motion compensation in the motion compensation unit 169.
Next, an explanation will be made of the flow of the processing for carrying out such encoding and generating an encoded bit stream having the structure shown in FIG. 2 by referring to FIG. 4.
FIG. 4 is a flow chart of the flow of the processing for generating a bit stream by carrying out MPEG encoding.
When the encoding is started (step S180), a sequence header is generated (step S181), a GOP header is generated (step S182), a picture header is generated (step S183), and a slice header is generated (step S184).
When the generation of headers of the different levels is ended, macroblock encoding is carried out (step S185), macroblock variable length coding is carried out (step S186), and macroblock local decoding is carried out (step S187).
When the encoding is ended for all macroblocks inside a slice, the processing routine, shifts to the processing of the next slice (step S188). Below, similarly, when all processing of a picture is ended, the processing routine shifts to the processing of the next picture (step S189). When all processing of one GOP is ended, the processing routine shifts to the processing of the next GOP (step S190). This series of processing is repeated until the sequence is ended (step S191), whereupon the processing is ended (step S192).
A timing chart showing the sequential execution of such encoding by a processor, for example, a digital signal processor (DSP), is shown in FIG. 5.
As shown in FIG. 5, in the processor, the processing of the flow chart shown in FIG. 4 is sequentially carried out for every macroblock.
Note that, in FIG. 5, the processing “MBx-ENC” indicates the encoding with respect to the data of an (x+1)th macroblock x, the processing “MBx-VLC” indicates variable length coding with respect to the data of the (x+1)th macroblock x, and the processing “MBx-DEC” indicates the local encoding with respect to the data of the (x+1)th macroblock x.
Next, an explanation will be made of the decoding.
FIG. 6 is a block diagram of the configuration of a general processing unit for carrying out the MPEG decoding.
A decoding apparatus 200 shown in FIG. 6 has a variable length decoding unit (VLD) 201, an inverse quantization unit (IQ) 202, an inverse discrete cosine transform unit (IDCT) 203, an adder 204, a motion compensation unit (MC) 205, and a decode control unit 206.
In a decoding apparatus 200 having such a configuration, a bit stream of the input encoded data is decoded at the variable length decoding unit 201 to separate the encoding mode, motion vector, quantization information, and quantized DCT coefficient for every macroblock. The decoded quantized DCT coefficient is subjected to inverse quantization at the inverse quantization unit 202, restored to the DCT coefficient, subjected to IDCT by the inverse discrete cosine transform unit 203, and transformed to pixel space data.
When the block is in the motion compensation prediction mode, the motion compensation predicted block data is added at the adder 204 to restore and output the original data. Further, the motion compensation unit 205 carries out motion compensation prediction based on the decoded image to generate the data to be added at the adder 204.
Note that the decode control unit 206 controls the operations of these units of the decoding apparatus 200.
Note that such decoding may be generally roughly classified into processing at two processing units, that is, the variable length decoding at the variable length decoding unit 201 for decoding the bit stream and the decoding from the inverse quantization in the inverse quantization unit 202 to the motion compensation in the motion compensation unit 205.
Next, an explanation will be made of the flow of the processing for carrying out such decoding to decode an encoded bit stream having the structure shown in FIG. 2 by referring to FIG. 7.
FIG. 7 is a flow chart showing the flow of the processing for generating the original image data by carrying out MPEG decoding.
When the decoding is started (step S210), the sequence header is decoded (step S211), the GOP header is decoded (step S212), the picture header is decoded (step S213), and the slice header is decoded (step S214).
When the decoding of the headers of the different levels is ended, macroblock variable length decoding is carried out (step S215), and decoding of the macroblock is carried out (step S216).
When the decoding is ended for all macroblocks inside the slice, the processing routine shifts to the processing of the next slice (step S217). Below, similarly, when all processing of one picture is ended, the processing routine shifts to the processing of the next picture (step S218), and when all processing of one GOP is ended, the processing routine shifts to the processing of the next GOP (step S219). This series of processings is repeated until the sequence is ended (step S220), whereupon the processing is ended (step S221).
A timing chart of the sequential execution of such decoding by a processor, for example, a DSP, is shown in FIG. 8.
As shown in FIG. 8, in the processor, processing of the flow chart shown in FIG. 7 is sequentially carried out for every slice and for every macroblock inside each slice.
Note that, in FIG. 8, the processing “SH-VLD” indicates the slice header decoding, the processing “MBx-VLD” indicates the variable length decoding with respect to the encoded data of the (x+1)th macroblock x, and the processing “MBx-DEC” indicates the decoding with respect to the encoded data of the (x+1)th macroblock x.
Summarizing the disadvantage to be solved by the invention, there is a demand that such encoding and decoding of image and other data be efficiently carried out at a high speed by a parallel processor having a plurality of processors. However, the parallel processors and parallel processing methods heretofore have suffered from various disadvantages, so have not been able to carry out high speed processing with a sufficiently high efficiency.
Specifically, first, when it is desired to carry out the encoding and decoding efficiently by parallel processing, there is a disadvantage that it is difficult to determine how to allocate which steps to the plurality of processors.
Further, in such encoding and decoding, since variable length data is to be processed, sequential processing must be carried out as the order of the data processing in the variable length coding and variable length decoding. For this reason, there is the disadvantage that the parallel processing is interrupted at the time of execution of the sequential processing parts or that the processing speed is limited since the sequential processing parts become an obstacle.
Further, if the times for execution of the processing in the processors are equal, the loads become uniform and equal and efficient processing can be carried out, but since the processing times of the different steps are different, there is a disadvantage that the loads of the processors become nonuniform and unequal and therefore high efficiency processing cannot be carried out.
Further, in such a parallel processing method, since in the case of for example the above image data, the processing with respect to one set of data like one video segment is carried out divided among a plurality of processors, it is necessary to carry out synchronization along with the transfer of the data or control the communication, so there is the disadvantage that the configuration of the hardware, the control method, etc. become complex.
Further, since the processing to be carried out at the different processors differ, processing programs must be prepared for the individual processors and the processing must be separately controlled for the individual processors, so there is the disadvantage that the configuration of the hardware, control method, etc. become even more complex.